package tree

import "fmt"

type BinaryTreeNode struct {
	Value int
	Left  *BinaryTreeNode
	Right *BinaryTreeNode
	Next  *BinaryTreeNode
}

func NewBinaryTreeNode(v int, l *BinaryTreeNode, r *BinaryTreeNode) *BinaryTreeNode {
	return &BinaryTreeNode{
		Value: v,
		Left:  l,
		Right: r,
	}
}

func (n *BinaryTreeNode) PrintVal() {
	fmt.Printf("%d ", n.Value)
}

func (n *BinaryTreeNode) Print(prefix string, hasSibling bool) {
	if hasSibling {
		fmt.Printf("%s├──%d\n", prefix, n.Value)
	} else {
		fmt.Printf("%s└──%d\n", prefix, n.Value)
	}
}

type BinaryTree struct {
	Root *BinaryTreeNode
}

// BuildBinaryTree 通过数组构建完全二叉树
func BuildBinaryTree(a []int) BinaryTree {
	return BinaryTree{
		Root: buildBinaryTree(a, 0),
	}
}

func buildBinaryTree(a []int, s int) *BinaryTreeNode {
	if nil == a || s >= len(a) {
		return nil
	}

	l := buildBinaryTree(a, 2*s+1)
	r := buildBinaryTree(a, 2*s+2)

	return NewBinaryTreeNode(a[s], l, r)
}

func (t *BinaryTree) Empty() bool {
	return nil == t || nil == t.Root
}

func (t *BinaryTree) Print() {
	if !t.Empty() {
		fmt.Printf("\n.\n")
		printSub(t.Root, "", false)
		fmt.Printf("\n")
	} else {
		fmt.Printf("this binary tree is empty!\n")
	}
}

func printSub(node *BinaryTreeNode, prefix string, hasSibling bool) {

	node.Print(prefix, hasSibling)

	if hasSibling {
		prefix = fmt.Sprintf("%s|  ", prefix)
	} else {
		prefix = fmt.Sprintf("%s   ", prefix)
	}

	if nil != node.Left {
		if nil != node.Right {
			printSub(node.Left, prefix, true)
			printSub(node.Right, prefix, false)
		} else {
			printSub(node.Left, prefix, false)
		}
	} else {
		if nil != node.Right {
			printSub(node.Right, prefix, false)
		}
	}

}
